#ifndef _L_DISJOINT_SET_120130_H
#define _L_DISJOINT_SET_120130_H

#include <ltypes.h>
#include <lmacros.h>
#include <lirregularTable.h>

#include <boost/assert.hpp>
#include <boost/noncopyable.hpp>

LLIB_BEGIN
namespace util {

/* The Disjoint Set class which provides "find" and
 * "merge" operations effectively.
 */
class DisjointSet : public boost::noncopyable {
public:
    /* The constructor with element number */
    explicit DisjointSet(Int32 size) {
        _sz = size;
        _set = new Int32[size];
        FOR(I,0,size) _set[I] = I;
    }

    /* The destructor */
    ~DisjointSet() {
        delete[] _set;
    }

    /* Find the group id of element */
    Int32 Find(Int32 elemId);

    /* Merge the two group including elem0 and elem1 */
    void Merge(Int32 elemId0, Int32 elemId1);

    /* Update disjoint set so that :
     * 1. Group id is equal to the first element id in group;
     * 2. Every element is directly link to group root.(which means every groups' height is 1)
     */
    void Arrange();

    /* Collect group infomation and output every groups.
     * Newly allocated.
     */
    IrregularTable<Int32>* GetGroups();

private:
    /* set size */
    Int32       _sz;

    /* set */
    Int32*      _set;

};

} // end of namespace util    
LLIB_END

#endif
